# 动态规划50题 https://www.bilibili.com/video/BV1aa411f7uT
# 8/50 解码方法
# leetcode第91题: https://leetcode.cn/problems/decode-ways/description/

def numDecodings(s: str) -> int:
    n = len(s)
    dp = [0] * n
    if int(s[0]) == 0:
        return 0
    if n < 2:
        return 1
    # 除去上面两种特殊情况, 第一个数字一定是可以编码的
    dp[0] = 1
    """下面只需要考虑两种情况:
    1. 当前字符s[i]是否可以编码: 只要 s[i] != 0 那么就一定可以编码, 所以dp[i] = dp[i-1]
    如 "999" -> (9,9,9)  
    2. 当前字符与前一个字符的组合s[i - 1:s + i]是否可以编码: 此时需要考虑 s[i - 1] != 0, 且 s[i - 1:s + i] <=26
    那么dp[i] = dp[i-2]
    如 "1123" -> (1,1) (11)                                     dp[2]=2
                 (1,1,2) (11,2) (1,12)                          dp[3]=3
                 (1,1,2,3) (11,2,3) (1,12,3) (11,23) (1,1,23)   dp[4]=5
    """
    for i in range(1, n):
        if s[i] != "0":  # 只需要考虑
            dp[i] += dp[i - 1]
        if i == 1 and int(s[i - 1:i + 1]) <= 26:
            dp[i] += 1
        if i > 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
            dp[i] += dp[i - 2]
    return dp[n - 1]


if __name__ == '__main__':
    s = "12"
    print(numDecodings(s))  # 2 它可以解码为 "AB"（1 2）或者 "L"（12）。
    s1 = "226"
    print(numDecodings(s1))  # 3 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
    s2 = "06"
    print(numDecodings(s2))  # 0 "06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。
    s3 = "11106"
    print(numDecodings(s3))  # 2 AAJF" ，将消息分组为 (1, 1, 10, 6); "KJF" ，将消息分组为 (11, 10, 6)
    s4 = "101"
    print(numDecodings(s4))  # 1
    s5 = "1123"
    print(numDecodings(s5))  # 5 (1, 1, 2, 3) (1, 1, 23) (1, 12, 3) (11, 2, 3)  (11, 23)
    # 1,1               11                              2
    # 1,1,2             11,2            1,12            3
    # 1,1,2,3  1,1,23   11,2,3 11,23    1,12,3          5
    s6 = "307"
    print(numDecodings(s6))  # 0
